package contest.dweek33;

/**
 * 没AC,技巧题
 * @author code_yc
 * @version 1.0
 * @date 2020/8/24 16:06
 */
public class Solution4 {

    private int N;
    private int M;
    private int directionInX[] = new int[]{-1, 0, 1, 0};
    private int directionInY[] = new int[]{0, 1, 0, -1};

    public boolean containsCycle(char[][] arr) {
        N = arr.length;
        M = arr[0].length;
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) {
                    if (isCycle(i, j, arr, visited, -1, -1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean isCycle(int x, int y, char arr[][], boolean visited[][], int parentX, int parentY) {
        visited[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int newX = x + directionInX[k];
            int newY = y + directionInY[k];
            // 当前移动到的位置有效  -- 当前位置元素和之前的元素相等 -- 当前位置不是之前的位置
            if (isValid(newX, newY) && arr[newX][newY] == arr[x][y] && !(parentX == newX && parentY == newY)) {
                if (visited[newX][newY] == true) {
                    // 如果最终会到最开始的位置，则返回true
                    return true;
                } else {
                    if (isCycle(newX, newY, arr, visited, x, y))
                        return true;
                }
            }
        }
        return false;
    }

    private boolean isValid(int x, int y) {
        return x < N && x >= 0 && y < M && y >= 0;
    }
}
